package jzOffer;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 郝文雪
 * @date 2022/7/18 17:10
 * @Description 重建二叉树
 */
public class JZ7 {
    Map<Integer,Integer> map=new HashMap<>();
    int[] pre;
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        this.pre=pre;
        for(int i=0;i<pre.length;i++){
            map.put(vin[i],i);
        }
        return build(0,0,vin.length-1);

    }
    private TreeNode build(int root,int l,int r){
        if(l>r) return null;
        TreeNode node=new TreeNode(pre[root]);
        int index=map.get(pre[root]);
        node.left=build(root+1,l,index-1);
        node.right=build(root+index-l+1,index+1,r);// i - left + root + 1含义为根节点索引 + 左子树长度 + 1
        return node;
    }
}
